package leetcode.f1t100;

import leetcode.struct.ListNode;

/**
 * 旋转(尾部元素放到最前方)N次链表
 * https://leetcode.com/problems/rotate-list/
 *
 * @Author lichongxiao
 * @Date 2022/10/25 16:20
 */
public class Q61_RotateList {

    public static void main(String[] args) {
        new Q61_RotateList().test();
    }

    private void test(){
        ListNode head = rotateRight(new ListNode(1,new ListNode(2,new ListNode(3,new ListNode(4,new ListNode(5,null))))), 12);
        while(head != null){
            System.out.println(head.val);
            head = head.next;
        }
    }

    public ListNode rotateRight(ListNode head, int k) {
        if(head == null || head.next == null){
            return head;
        }
        if(k == 0){
            return head;
        }
        ListNode cur = head,tail=head,newHead;
        int count = 0,move=0;
        while(cur != null){
            count++;
            tail = cur;
            cur = cur.next;
        }
        k = k % count;
        if(k == 0){
            return head;
        }
        cur = head;
        move = count - k;
        // 移动move步才找到新头部，但是要在前一步停下处理新尾部断链，所以要少循环一次
        for (int i = 1; i < move; i++) {
            cur = cur.next;
        }
        newHead = cur.next;
        cur.next = null;
        tail.next = head;
        return newHead;
    }
}
